1. Field of the Invention
This invention relates to data communications. The invention is particularly applicable to multipoint communication between computers over a communication network.
2. Prior Art and Other Considerations
The majority of computer communications currently take place as a controlled interaction between two computers. This is known as "point-to-point" interaction and is often achieved by means of a "virtual circuit" i.e. a logical connection between two computers established and controlled by the communication protocols used by them. Increasingly, it is necessary to establish "multipoint" communication protocols. This situation is analogous to that in other forms of multicast communications in which the transfer of information transmitted by a source is received by all receivers tuned to accept the information and which are switched on at the time of transmittal, for example a television transmission and reception system. Such a protocol should be both efficient and flexible and yet as simple a means of controlling communications between large groups of computers as possible.
A basic but relatively unreliable protocol is provided by, for example, the IEEE 802.2 Logical Link Control protocol which can be operated on local area networks (LANs). This and other protocols which operate on local and wide area networks provide multipoint datagram services, i.e. data is multicast to all receivers.
There are two basic techniques by which the correctness of the data received can be monitored by primary stations sending data to one or more secondaries. Both rely on the acknowledgement of a transmitted message by sending back to the originating primary an acknowledging message notifying the originator of the correct receipt of one or more previous messages.
Firstly, there is "positive acknowledgement", in which messages are acknowledged upon correct reception. If this acknowledgement is not detected by the sending primary station by a certain time, the message is retransmitted. This may be repeated up to a set number of attempts, after which the link will be declared failed. This is the standard method of error correction in a point-to-point link.
Secondly, there is "negative acknowledgement" in which a message is sent back by a secondary to the primary originator notifying the latter of a loss of one or more previous messages. Thus, each station need not acknowledge every message. However, there is a compromise with the need to keep a copy of any message not yet acknowledged, in case it has been lost. The less frequently each station acknowledges, the longer the uncertainty period and the more messages must be stored.
In "one-to-many", i.e. multipoint, communication it is impracticable to use positive acknowledgement as the number of returned acknowledgement mess ages could swamp the primary transmitting station and/or the network. Clearly, the problem becomes more acute with an increasingly large number of secondary stations. Thus, there is a need to limit the number of acknowledgements.
EP 263421 describes a "many-to-one" communications system which uses a basic form of restricted acknowledgement technique. In this case, the central station itself uses negative acknowledgement to respond to data messages from remote secondary stations, but employs a simple polling system to elicit acknowledgements from the secondaries as a means of checking that they are operational. The central station thus sends a polling request, which is independent of any data message, to each secondary in turn. The secondaries are then each required to respond to their respective polling request, with a response which merely acknowledges that the polling request has been received and that (by implication) the secondary concerned is operational. However, there is no special acknowledgement system with respect to other messages sent from the central station.
One method for doing this is to send "explicit" control information to the secondaries, either as part of a data packet or as separate messages, instructing them which messages to acknowledge. For example, one station (S.sub.1) may be instructed to acknowledge data message number 1 and every fiftieth message thereafter. Likewise, another station (S.sub.2) may be instructed to acknowledge message number 2 and every fiftieth message thereafter. This "priming" of secondary stations allows subsequent messages to be sent without such control information. As an alternative to this instruction of the secondary station acknowledgement, each data message itself can include a station "identifier" which requests the secondary to acknowledge either this or a particular subsequent message. This ongoing acknowledgement control is more suitable for dynamically changing groups where it is not practicable to predefine the entire sequence of responses as above. Since the instructions are relative to the current message, they are independent of any absolute sequence number that may be a part of the message.
U.S. Pat. No. 4,725,834 describes a scheme whereby a single recipient secondary in a multipoint communication system is designated as a "token site" and is responsible for acknowledging the received multicast message. All the other sites in a group "listen" to both the primary originator of the message and to the acknowledgements from the token sites. Should any of the secondaries detect a gap in the messages it receives, based on the monitoring of both the messages and the acknowledgements, it may request a retransmission from the token site. By rotating the token site amongst all recipients in a group, it is possible to ensure reliable reception of all messages at all sites with less acknowledgement than is required in a less sophisticated scheme.
Thus, there is a method of data communication between a primary source and a group of secondary receivers which comprises:
transmitting data messages from the source to the receivers;
transmitting an acknowledgement from a receiver, on correct receipt of a data message transmitted; and
storing, in buffer storage means, a set of latest data messages, for retransmission of at least one of the said set in the event that no acknowledgement of at least that said one of the said set of data messages is received successfully by the source.
However, one problem to arise when such a scheme as this is implemented is that all members of a group must maintain an accurate list of the group membership. This requires a complex reformation protocol (as described in U.S. Pat. No. 4,725,834) in the event of even a single secondary station failure.
Another problem is that an increase in the group size requires a proportionate increase in the capacity of the buffer storage at each secondary. Either this, or the number of instruction messages used to rotate the designation of the token site must increase proportionately.
The scheme is also inefficient in that all acknowledgements must be processed by all group members. For some applications the strict ordering of messages from different sources required by this protocol is excessively elaborate. On the one hand, this works well for ensuring the consistency of a distributed database, such as the local area network (LAN) for which it was designed. On the other hand, this imposes an excessively long completion time on each transmission which would be unacceptable in certain other applications.